/*
 * @Author: your name
 * @Date: 2020-09-09 10:49:18
 * @LastEditTime: 2020-09-09 11:07:41
 * @LastEditors: Please set LastEditors
 * @Description: In User Settings Edit
 * @FilePath: /QuickSort/QuickSort.cpp
 */
#include <iostream>

using namespace std;

//快速排序
void quicksort(int arry[],int left, int right) 
{
	if(left > right)
		return;
    int temp = arry[left]; //temp中存的就是基准数
    int i = left;
    int j = right;
    while(i != j) { //顺序很重要，要先从右边开始找
    	while(arry[j] >= temp && i < j)
    		j--;
    	while(arry[i] <= temp && i < j)//再找右边的
    		i++;       
    	if(i < j)//交换两个数在数组中的位置
    	{
    		int t = arry[i];
    		arry[i] = arry[j];
    		arry[j] = t;
    	}
    }
    //最终将基准数归位
    arry[left] = arry[i];
    arry[i] = temp;
    quicksort(arry,left, i-1);//继续处理左边的，这里是一个递归的过程
    quicksort(arry,i+1, right);//继续处理右边的 ，这里是一个递归的过程
}

int main()
{
	int arry[8]={10,48,93,67,42,89,57,29};
	for (int i = 0; i < 8; i++)
	{
		cout<<arry[i]<<' ';
	}
	cout<<endl;
	quicksort(arry,0,7);
	for (int i = 0; i < 8; i++)
	{
		cout<<arry[i]<<' ';
	}
	cout<<endl;
	return 0;
}
